해쉬 테이블
간단히 말하자면, 여러 자료들을 분류한뒤 해시 함수를 이용해서 자료를 찾을 수 있게 만드는 방법을 말한다. 그 과정에서 충돌 등의 문제가 발생하며 이를 해결하는 방법들을 배운다.
해싱이란
임의의 값을 해시 하수를 사용해서 고정된 크기의 값으로 변환하는 작업을 말한다.
해싱을 사용하요 데이터를 저장하는 자료구조를 해시 테이블이라고 하며, 이를 이용하면 기존 자료구조를 사용한 이진탐색 트리나 배열에 비해서 굉장하게 빠른 속도로 탐색, 삽입, 삭제를 할 수 있다.
해시 테이블
해시 함수를 사용하여 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다.
기본연산으로 탐색, 삽입, 삭제가 가능하다.
direct address table
key값을 주소로 사용하는 테이블을 말한다.
사실 해시 테이블이라고 말하기도 뭐할 정도로 간단한 형태이다.
https://www.geeksforgeeks.org/direct-address-table/
예를 들면 key값이 21인 value를 인덱스 21에 저장한다.
탐색, 삭제, 연산 모두 O(1) 이지만, 키값이 골고루 분포되어 있지 않으면 메모리 낭비가 심하다.
hash table
해시 함수를 사용해서 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 갑과 데이터를 저장하는 자료구조이다.
이렇게 할경우 충돌의 문제가 발생할 수 있다.
적재율에 대해서 알아야하는데 적재율은 해시 테이블의 크기 대비, 키의 개수를 말한다.
키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이 된다.
결국 충돌을 줄여서 연산 속도를 빠르게 해야한다.
해시 함수
해시테이블 충돌 완화방법
open address 개방 주소법
해시값에 이미 데이터가 있을 경우다른 주소를 이용하는 방법이다.
https://en.wikipedia.org/wiki/Hash_table#Open_addressing
이 경우 이미 해시 값에 대한 인덱스가 차있는 경우 다음 인덱스로 이동하면서 비어 있는 곳을 찾는 것을 반복한다. 이를 probing이라고 한다.
이 probing 방식도 여러가지가 있다.
-
linear probing(선형 탐사)
바로 인접한 인덱스에 데이터를 삽입하는 방법.
데이터가 밀집하게 되어서 클러스터링 문제가 발생한다. -
quadratic probing(제곱 탐사)
인덱스를 제곱해서 탐사한다. 넓은 지역을 탐색하고 사용하기 떄문에 탐색과 삭제에 효율적이라고 한다.
이 방법도 초기 해시 값이 같으면 클러스터링 문제 발생한다고 한다.
-
double hashing(이중 해싱)
처음에는 해시 함수는 해시값을 찾기 위해 사용하고 두번째 해시함수는 probing 폭을 계산하기 위해 사용하는 이중 해싱 방법이다.
seprate chainin 분리 연결
충돌이 발생했을 때 동일한 버킷에 연결리스트 형태로 체이닝으로 저장하는 방법을 말한다.
삽입의 경우 연결리스트 추가이기 때문에 O(1)이 걸린다.
연결리스트의 특성상 탐색과 삭제의 경우에는 최악에 경우에는 키 값의 개수가 K 일 때 O(K) 이 걸릴 수 있다.
해시 구현
class Hash_table:
def __init__(self, length = 5):
self.max_len = length
self.table = [[] for _ in range(self.max_len)]
def hash(self, key):
res = sum([ord(s) for s in key])
return res % self.max_len
def set(self, key, value): #해시 테이블에 key와 value를 넣는다.
index = self.hash(key)
self.table[index].append((key, value))
def get(self, key): #해시 테이블에서 key의 value를 찾는다.
index = self.hash(key)
value = self.table[index]
if not value: #찾는 키가 없으면 None을 반환
return None
for v in value: #리스트에서 값을 찾아 반환
if v[0] == key:
return v[1]
return None